<html lang="zh-CN"><head><meta charset="UTF-8"><style>.nodata  main {width:1000px;margin: auto;}</style></head><body class="nodata " style=""><div class="main_father clearfix d-flex justify-content-center " style="height:100%;"> <div class="container clearfix " id="mainBox"><main><div class="blog-content-box">
<div class="article-header-box">
<div class="article-header">
<div class="article-title-box">
<h1 class="title-article" id="articleContentId">(A卷,200分)- 开放日活动、取出尽量少的球（Java & JS & Python）</h1>
</div>
</div>
</div>
<div id="blogHuaweiyunAdvert"></div>

        <div id="article_content" class="article_content clearfix">
        <link rel="stylesheet" href="https://csdnimg.cn/release/blogv2/dist/mdeditor/css/editerView/kdoc_html_views-1a98987dfd.css">
        <link rel="stylesheet" href="https://csdnimg.cn/release/blogv2/dist/mdeditor/css/editerView/ck_htmledit_views-044f2cf1dc.css">
                <div id="content_views" class="htmledit_views">
                    <h4 id="main-toc">题目描述</h4> 
<p><span style="color:#0d0016;">某部门开展<strong>Family Day</strong>开放日活动&#xff0c;其中有个从桶里取球的游戏&#xff0c;游戏规则如下&#xff1a;</span></p> 
<p><span style="color:#0d0016;">有N个容量一样的小桶等距排开&#xff0c;</span></p> 
<p><span style="color:#0d0016;">且每个小桶都默认装了数量不等的小球&#xff0c;</span></p> 
<p><span style="color:#0d0016;">每个小桶装的小球数量记录在数组 bucketBallNums 中&#xff0c;</span></p> 
<p><span style="color:#0d0016;">游戏开始时&#xff0c;要求所有桶的小球总数不能超过SUM&#xff0c;</span></p> 
<p><span style="color:#0d0016;">如果小球总数超过SUM&#xff0c;则需对所有的小桶统一设置一个容量最大值 maxCapacity&#xff0c;</span></p> 
<p><span style="color:#0d0016;">并需将超过容量最大值的小球拿出来&#xff0c;直至小桶里的小球数量小于 maxCapacity;</span></p> 
<p><span style="color:#0d0016;">请您根据输入的数据&#xff0c;计算从每个小桶里拿出的小球数量。</span></p> 
<p><span style="color:#0d0016;">限制规则一&#xff1a;</span></p> 
<p><span style="color:#0d0016;">所有小桶的小球总和小于SUM&#xff0c;则无需设置容量值maxCapacity&#xff0c;并且无需从小桶中拿球出来&#xff0c;返回结果[]</span></p> 
<p><span style="color:#0d0016;">限制规则二&#xff1a;</span></p> 
<p><span style="color:#0d0016;">如果所有小桶的小球总和大于SUM&#xff0c;则需设置容量最大值maxCapacity&#xff0c;并且需从小桶中拿球出来&#xff0c;返回从每个小桶拿出的小球数量组成的数组&#xff1b;</span></p> 
<p></p> 
<h4 id="%E8%BE%93%E5%85%A5%E6%8F%8F%E8%BF%B0">输入描述</h4> 
<p>第一行输入2个正整数&#xff0c;数字之间使用空格隔开&#xff0c;其中第一个数字表示SUM&#xff0c;第二个数字表示bucketBallNums数组长度&#xff1b;<br /> 第二行输入N个正整数&#xff0c;数字之间使用空格隔开&#xff0c;表示bucketBallNums的每一项&#xff1b;</p> 
<p></p> 
<h4 id="%E8%BE%93%E5%87%BA%E6%8F%8F%E8%BF%B0">输出描述</h4> 
<p>找到一个maxCapacity&#xff0c;来保证取出尽量少的球&#xff0c;并返回从每个小桶拿出的小球数量组成的数组。</p> 
<p></p> 
<h4>备注</h4> 
<ul><li>1 ≤ bucketBallNums[i] ≤ 10^9</li><li>1 ≤ bucketBallNums.length &#61; N ≤ 10^5</li><li>1 ≤ maxCapacity ≤ 10^9</li><li>1 ≤ SUM ≤ 10^9</li></ul> 
<p></p> 
<h4 id="%E7%94%A8%E4%BE%8B">用例</h4> 
<table border="1" cellpadding="1" cellspacing="1" style="width:538px;"><tbody><tr><td style="width:86px;">输入</td><td style="width:448px;">14 7<br /> 2 3 2 5 5 1 4</td></tr><tr><td style="width:86px;">输出</td><td style="width:448px;">[0,1,0,3,3,0,2]</td></tr><tr><td style="width:86px;">说明</td><td style="width:448px;">小球总数为22&#xff0c;SUM&#61;14&#xff0c;超出范围了&#xff0c;需从小桶取球&#xff0c;<br /> maxCapacity&#61;1&#xff0c;取出球后&#xff0c;桶里剩余小球总和为7&#xff0c;远小于14<br /> maxCapacity&#61;2&#xff0c;取出球后&#xff0c;桶里剩余小球总和为13&#xff0c;<br /> maxCapacity&#61;3&#xff0c;取出球后&#xff0c;桶里剩余小球总和为16&#xff0c;大于14<br /> 因此maxCapacity为2 &#xff0c;每个小桶小球数量大于2的都需要拿出来&#xff1b;</td></tr></tbody></table> 
<table border="1" cellpadding="1" cellspacing="1" style="width:542px;"><tbody><tr><td style="width:88px;">输入</td><td style="width:452px;">3 3<br /> 1 2 3</td></tr><tr><td style="width:88px;">输出</td><td style="width:452px;">[0,1,2]</td></tr><tr><td style="width:88px;">说明</td><td style="width:452px;">小球总数为6&#xff0c;SUM&#61;3&#xff0c;超出范围了&#xff0c;需从小桶中取球&#xff0c;maxCapacity&#61;1&#xff0c;则小球总数为3&#xff0c;从1号桶取0个球&#xff0c;2号桶取1个球&#xff0c;3号桶取2个球&#xff1b;</td></tr></tbody></table> 
<table border="1" cellpadding="1" cellspacing="1" style="width:547px;"><tbody><tr><td style="width:90px;">输入</td><td style="width:456px;">6 2<br /> 3 2</td></tr><tr><td style="width:90px;">输出</td><td style="width:456px;">[]</td></tr><tr><td style="width:90px;">说明</td><td style="width:456px;">小球总数为5&#xff0c;SUM&#61;6&#xff0c;在范围内&#xff0c;无需从小桶取球&#xff1b;</td></tr></tbody></table> 
<p></p> 
<h4 id="%E9%A2%98%E7%9B%AE%E8%A7%A3%E6%9E%90">题目解析</h4> 
<p>用例示意图如下&#xff1a;</p> 
<p>由于所有桶中的球数之和超过了14&#xff0c;因此我们需要设置一个<span style="color:#0d0016;">maxCapacity</span>来限制每个桶中球的数量。</p> 
<p>如果maxCapacity值设置为0&#xff0c;则所有桶中的球都需要取出&#xff0c;因此剩余球总数为0&#xff0c;小于sum&#61;14,因此符合要求</p> 
<p><img alt="" height="344" src="https://img-blog.csdnimg.cn/2f0aff259d714c6db22d80f82da82bab.png" width="818" /></p> 
<p></p> 
<p>如果maxCapacity值设置为1&#xff0c;则所有桶中的球最多只保留1个&#xff0c;如下图所示&#xff0c;剩余球总数7个&#xff0c;也符合要求</p> 
<p><img alt="" height="364" src="https://img-blog.csdnimg.cn/aa698e27c7464949b079c2e6c0a2800c.png" width="855" /></p> 
<p></p> 
<p>如果maxCapacity值设置为2&#xff0c;则所有桶中的球最多只保留2个&#xff0c;如下图所示&#xff0c;剩余球总数13个&#xff0c;也符合要求</p> 
<p><img alt="" height="356" src="https://img-blog.csdnimg.cn/1dbbdacd961e4bc3874476c9bfc991fc.png" width="832" /></p> 
<p>如果maxCapacity值设置为3&#xff0c;则所有桶中的球最多只保留3个&#xff0c;如下图所示&#xff0c;剩余球总数17个&#xff0c;不符合要求</p> 
<p><img alt="" height="360" src="https://img-blog.csdnimg.cn/a0ea9ee6311644e189f01096c09937c5.png" width="836" /></p> 
<p>因此&#xff0c;我们可以发现&#xff0c;maxCapacity取值2时&#xff0c;剩余球数最多&#xff0c;总数量小于SUM&#61;14&#xff0c;符合要求&#xff0c;且取出的球最少&#xff0c;分别为0&#xff0c;1&#xff0c;0&#xff0c;3&#xff0c;3&#xff0c;0&#xff0c;2。</p> 
<p></p> 
<p>那么我们是否需要从maxCapacity&#61;0开始找呢&#xff1f;</p> 
<p>答案是不需要&#xff0c;我们完全可以使用 SUM / <span style="color:#0d0016;">bucketBallNums.length </span>求得一个最理想值.</p> 
<p>比如用例中SUM&#61;14&#xff0c;bucketBallNums.length&#61;7&#xff0c;则每个桶中球数量的最理想值是14/7&#61;2。</p> 
<p>我们可以将此时最理想值作为maxCapacity的起始值。然后向后查找。</p> 
<p></p> 
<p>但是上面这种算法在应对较大数量级&#xff0c;可能会超时&#xff0c;因此改进策略是使用二分查找&#xff0c;具体逻辑请看</p> 
<p><a href="https://fcqian.blog.csdn.net/article/details/128746852" rel="nofollow" title="华为OD机试 - 日志限流_伏城之外的博客-CSDN博客">华为OD机试 - 日志限流_伏城之外的博客-CSDN博客</a></p> 
<p></p> 
<h4 id="%E7%AE%97%E6%B3%95%E6%BA%90%E7%A0%81">JavaScript算法源码</h4> 
<pre><code class="language-javascript">/* JavaScript Node ACM模式 控制台输入获取 */
const readline &#61; require(&#34;readline&#34;);

const rl &#61; readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const lines &#61; [];
rl.on(&#34;line&#34;, (line) &#61;&gt; {
  lines.push(line);

  if (lines.length &#61;&#61;&#61; 2) {
    const [sum, n] &#61; lines[0].split(&#34; &#34;).map(Number);
    const arr &#61; lines[1].split(&#34; &#34;).map(Number);
    console.log(getResult(sum, arr, n));
    lines.length &#61; 0;
  }
});

function getResult(sum, arr, n) {
  const total &#61; arr.reduce((p, c) &#61;&gt; p &#43; c);

  if (total &lt;&#61; sum) return &#34;[]&#34;;

  let max_maxCapacity &#61; Math.max.apply(null, arr);
  let min_maxCapacity &#61; Math.floor(sum / n);

  // ans保存题解&#xff0c;初始题解为min_maxCapacity对应的题解
  let ans &#61; arr.map((count) &#61;&gt;
    count &gt; min_maxCapacity ? count - min_maxCapacity : 0
  );

  while (max_maxCapacity - min_maxCapacity &gt; 1) {
    const maxCapacity &#61; Math.floor((max_maxCapacity &#43; min_maxCapacity) / 2);

    let remain &#61; total;

    // tmp数组保存的是每个桶移除的球的数量
    const tmp &#61; arr.map((count) &#61;&gt; {
      // r是每个桶需要移除的球的个数&#xff0c;如果桶内球数超过maxCapacity&#xff0c;则需要移除超出部分&#xff0c;否则不需要移除
      const r &#61; count &gt; maxCapacity ? count - maxCapacity : 0;
      remain -&#61; r;
      return r;
    });

    if (remain &gt; sum) {
      max_maxCapacity &#61; maxCapacity;
    } else if (remain &lt; sum) {
      min_maxCapacity &#61; maxCapacity;
      ans &#61; tmp;
    } else {
      ans &#61; tmp;
      break;
    }
  }

  return JSON.stringify(ans);
}
</code></pre> 
<p></p> 
<h4>Java算法源码</h4> 
<p>考虑total会超过int范围&#xff0c;所以total设置为long类型。以及remain也设置为long类型。</p> 
<pre><code class="language-java">import java.util.Arrays;
import java.util.Scanner;
import java.util.StringJoiner;

public class Main {
  public static void main(String[] args) {
    Scanner sc &#61; new Scanner(System.in);

    int sum &#61; sc.nextInt();
    int n &#61; sc.nextInt();

    Integer[] arr &#61; new Integer[n];
    for (int i &#61; 0; i &lt; n; i&#43;&#43;) {
      arr[i] &#61; sc.nextInt();
    }

    System.out.println(getResult(sum, arr, n));
  }

  public static String getResult(int sum, Integer[] arr, int n) {
    long total &#61; 0;
    int max_maxCapacity &#61; 0;
    for (int i &#61; 0; i &lt; n; i&#43;&#43;) {
      max_maxCapacity &#61; Math.max(max_maxCapacity, arr[i]);
      total &#43;&#61; arr[i];
    }

    if (total &lt;&#61; sum) return &#34;[]&#34;;

    int min_maxCapacity &#61; sum / n;

    final int min_maxCapacity_copy &#61; min_maxCapacity;
    Integer[] ans &#61;
        Arrays.stream(arr)
            .map(count -&gt; count &gt; min_maxCapacity_copy ? count - min_maxCapacity_copy : 0)
            .toArray(Integer[]::new);

    while (max_maxCapacity - min_maxCapacity &gt; 1) {
      int maxCapacity &#61; (max_maxCapacity &#43; min_maxCapacity) / 2;

      // tmp数组保存的是每个桶移除的球的数量
      Integer[] tmp &#61; new Integer[n];
      long remain &#61; total;
      for (int i &#61; 0; i &lt; arr.length; i&#43;&#43;) {
        // r是每个桶需要移除的球的个数&#xff0c;如果桶内球数超过maxCapacity&#xff0c;则需要移除超出部分&#xff0c;否则不需要移除
        int r &#61; arr[i] &gt; maxCapacity ? arr[i] - maxCapacity : 0;
        remain -&#61; r;
        tmp[i] &#61; r;
      }

      if (remain &gt; sum) {
        max_maxCapacity &#61; maxCapacity;
      } else if (remain &lt; sum) {
        min_maxCapacity &#61; maxCapacity;
        ans &#61; tmp;
      } else {
        ans &#61; tmp;
        break;
      }
    }

    StringJoiner sj &#61; new StringJoiner(&#34;,&#34;, &#34;[&#34;, &#34;]&#34;);
    for (Integer an : ans) {
      sj.add(an &#43; &#34;&#34;);
    }

    return sj.toString();
  }
}
</code></pre> 
<h4>Python算法源码</h4> 
<pre><code class="language-python"># 输入获取
sumV, n &#61; map(int, input().split())
arr &#61; list(map(int, input().split()))


# 算法入口
def getResult(sumV, arr, n):
    total &#61; sum(arr)

    if total &lt;&#61; sumV:
        return &#34;[]&#34;

    max_maxCapacity &#61; max(arr)
    min_maxCapacity &#61; int(sumV / n)

    # ans保存题解&#xff0c;初始题解为min_maxCapacity对应的题解
    ans &#61; list(map(lambda count: count - min_maxCapacity if count &gt; min_maxCapacity else 0, arr))

    while max_maxCapacity - min_maxCapacity &gt; 1:
        maxCapacity &#61; int((max_maxCapacity &#43; min_maxCapacity) / 2)

        # tmp数组保存的是每个桶移除的球的数量
        tmp &#61; list(map(lambda count: count - maxCapacity if count &gt; maxCapacity else 0, arr))

        remain &#61; total - sum(tmp)
        if remain &gt; sumV:
            max_maxCapacity &#61; maxCapacity
        elif remain &lt; sumV:
            min_maxCapacity &#61; maxCapacity
            ans &#61; tmp
        else:
            ans &#61; tmp
            break

    return &#34;[&#34; &#43; &#34;,&#34;.join(map(str, ans)) &#43; &#34;]&#34;


# 调用算法
print(getResult(sumV, arr, n))
</code></pre>
                </div>
        </div>
        <div id="treeSkill"></div>
        <div id="blogExtensionBox" style="width:400px;margin:auto;margin-top:12px" class="blog-extension-box"></div>
    <script>
  $(function() {
    setTimeout(function () {
      var mathcodeList = document.querySelectorAll('.htmledit_views img.mathcode');
      if (mathcodeList.length > 0) {
        for (let i = 0; i < mathcodeList.length; i++) {
          if (mathcodeList[i].naturalWidth === 0 || mathcodeList[i].naturalHeight === 0) {
            var alt = mathcodeList[i].alt;
            alt = '\\(' + alt + '\\)';
            var curSpan = $('<span class="img-codecogs"></span>');
            curSpan.text(alt);
            $(mathcodeList[i]).before(curSpan);
            $(mathcodeList[i]).remove();
          }
        }
        MathJax.Hub.Queue(["Typeset",MathJax.Hub]);
      }
    }, 1000)
  });
</script>
</div></html>